Several methods for providing volumetric representations of three-dimensional objects are known in the art. An example of a method for providing volumetric representations of three-dimensional objects includes providing a three-dimensional (3D) shape reconstruction of objects from multiple views. The computation of the visual hull from object silhouettes is a popular technique.
The method, also called shape-from-silhouette, delivers a 3D description of the object. The approach requires a set of silhouette images from calibrated cameras. A silhouette image is a binary (or in some cases, gray scale) image where each pixel indicates whether this pixel belongs to the object or not. The silhouette information can be determined by any suitable segmentation process. This is advantageously done using chroma-keying or difference-keying as described in our GB-0220972.4 and our earlier applications referred therein.
The 3D shape reconstruction can be formulated as the intersection of generalized cones of the silhouette images. A generalized cone is the union of visual rays from all silhouette points of a particular image. This intersection gives only an approximation of the real object shape and is called the visual hull. In particular concavities cannot be modelled with this method.
Several algorithms have been published for the computation of the visual hull, for example: W. Martin and J. K. Aggarwal, “Volumetric descriptions of objects from multiple views,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 5, no. 2, pp. 150-158, March 1983; M. Potmesil, “Generating octree models of 3D objects from their silhouettes in a sequence of images,” Computer Vision, Graphics and Image Processing, vol. 40, pp. 1-29, 1987; Richard Szeliski, “Rapid octree construction from image sequences,” CVGIP: Image Understanding, vol. 58, no. 1, pp. 23-32, July 1993; and Wolfgang Niem, “Robust and fast modelling of 3d natural objects from multiple views,” in SPIE Proceedings, Image and Video Processing II, San Jose, February 1994, vol. 2182, pp. 388-397. These approaches attempt to solve the problem in a volumetric space representation. The most common of these representations is to subdivide a 3D box in Euclidian 3D-space into a set of voxels of discrete size. The size of the box is predetermined such that the object can fit inside. In order to save memory these may be represented as “octrees” or are run-length encoded.
For the use of the 3D reconstruction, e.g. in a computer graphic application, a surface description, usually a polygonal mesh has to be generated. An often used algorithm is the marching cubes algorithm, described in U.S. Pat. Nos. 4,710,876, 4,719,585, 4,885,688 and at http://www.exaflop.org/docs/marchcubes/ind.html, the contents of which are all incorporated herein by reference, which creates an iso-surface of a volumetric data set, the iso-surface being made up of contiguous triangles having vertices positioned at mid-points of voxel edges. Since the mentioned shape-from-silhouette methods compute binary voxels the 3D surfaces generated from those using the marching cube algorithm are very noisy. This noise is introduced due to spatial discretization of the volumetric representations. That is to say, real data of the actual shape of the object is lost during the processing of the algorithm.
An improvement over the prior art is described in the applicant's U.K. Patent Publication Number 2 399 703, which discloses combining voxel data with data obtained by projecting line sets into 2 dimensional representations of a 3 dimensional object. The combined data is then used in the above mentioned marching cubes algorithm such that the position of the generated iso-surface triangle vertices is more accurately positioned on respective voxel edges. While this improved method is useful, it tends to use heavily available processing power.
Another problem with volumetric reconstructions from silhouette images is that of redundant voxels which occur due to the approximation errors in the reconstructed 3D volumetric representation when a small number of cameras are used. The reconstruction is always bigger than the actual object. This error is exacerbated when reconstructing volumetric representations of moving objects. When an object moves, the edges formed by two adjacent camera views move relatively over the object, resulting in a reconstruction which is visibly quite disturbing to the viewer.